import itertools
import collections
class Solution:
    def minimumIncompatibility(self, nums, k: int) -> int:
        n = len(nums)
        m = n // k
        candidate = {}
        for st in itertools.combinations(range(n), m):
            already = set()
            val = 0
            flag = True
            max_val = 0
            min_val = float('inf')
            for c in st:
                if nums[c] in already:
                    flag = False
                    break
                else:
                    already.add(nums[c])
                    max_val = max(max_val, nums[c])
                    min_val = min(min_val, nums[c])
                    val |= (1 << c)
            if flag:
                candidate[val] = max_val - min_val
        now_set = {0:0}
        index = 0
        while index < k:
            index += 1
            next_set = collections.defaultdict(lambda: float('inf'))
            for l_key, l_value in now_set.items():
                for r_key, r_value in candidate.items():
                    if l_key & r_key == 0:
                        next_set[l_key | r_key] = min(l_value + r_value, next_set[l_key | r_key])
            now_set = next_set
        if now_set:
            return min(now_set.values())
        else:
            return -1







data = Solution()
nums = [7,3,16,15,1,13,1,2,14,5,3,10,6,2,7,15]
k = 8
print(data.minimumIncompatibility(nums, k))
